package com.fpp.leetcode;

import java.util.HashMap;
import java.util.Map;

public class LRU {
}

class LRUCache {

    private final int capacity;

    private final  Map<Integer, Node> cache;
    /**
     *
     */
    private final Node head;
    /**
     * 如果容量满了 就移除链表尾部的
     */
    private final Node tail;

    static class Node{
        public Integer key;
        public Integer value;
        public Node next;
        public Node prev;

        public Node(Integer key, Integer value, Node next, Node prev) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.prev = prev;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    ", prev=" + prev +
                    '}';
        }
    }

    public LRUCache(int capacity) {
        this.capacity=capacity;
        this.cache = new HashMap<Integer,Node>();
        this.head = new Node();
        this.tail=new Node();
        this.head.next =tail;
        this.tail.prev = head;


    }

    public int get(int key) {
        Node node = cache.get(key);
        if(null==node){
            return -1;
        }
        //如果获取到了元数则将元数移到头部
        removeNode(node);
        moveToHead(node);
        return node.value;
    }

    public void moveToHead(Node node){
        node.next=head.next;
        node.prev=head;
        Node next=head.next;
        head.next=node;
        next.prev=node;
    }

    public void removeNode(Node node){
        Node prev =node.prev;
        Node next = node.next;
        prev.next=next;
        next.prev=prev;
    }


    public void put(int key, int value) {
        Node exists = cache.get(key);
        if(null==exists&&cache.size()==capacity){
            Node node = new Node(key, value, null, null);
            //去除尾部的最不经常使用的原来的那个节点
            Node removeNode=tail.prev;
            removeNode(removeNode);
            cache.remove(removeNode.key);
            moveToHead(node);
            cache.put(key, node);
            return;
        }
        if(null==exists) {
            Node node = new Node(key, value, null, null);
            cache.put(key, node);
            moveToHead(node);
        }else{
            exists.value=value;
            removeNode(exists);
            moveToHead(exists);
        }
    }
}
